// 模拟
// 思路比较简单 - 直接根据题目要求进行模拟
// 一定要在演草纸上手动模拟算法流程，避免凭空想象
// 难度高的模拟题，往往都需要找规律，才能简化，否则代码不好写，并且时间/空间复杂度较高

// 例题 4：
//「外观数列」是一个数位字符串序列，由递归公式定义：
//
//        countAndSay(1) = "1"
//        countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
//
//        行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）
//        替换为字符重复次数（运行长度）和字符的串联。
//        例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，
//        将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。
//        因此压缩后字符串变为 "23321511"。
//
//        给定一个整数 n ，返回 外观数列 的第 n 个元素。
//
//        示例 1：
//
//        输入：n = 4
//
//        输出："1211"
//
//        解释：
//
//        countAndSay(1) = "1"
//
//        countAndSay(2) = "1" 的行程长度编码 = "11"
//
//        countAndSay(3) = "11" 的行程长度编码 = "21"
//
//        countAndSay(4) = "21" 的行程长度编码 = "1211"
//
//        示例 2：
//
//        输入：n = 1
//
//        输出："1"
//
//        解释：
//
//        这是基本情况。
//
//
//
//        提示：
//
//        1 <= n <= 30
//
//
//        进阶：你能迭代解决该问题吗？

// 解题思路：
// 模拟题目中的过程，实际上就是在遍历一个字符串并解释
// 遍历一个字符串进行解释，类似于找子串的问题，可以借助双指针的思路

public class CountAndSay {
    public String countAndSay(int n) {
        if(n == 1) return "1";
        StringBuilder s = new StringBuilder();
        s.append("1");
        for(int i = 2; i <= n; i++){
            StringBuilder tmp = new StringBuilder();
            int len = s.length();
            int left = 0;
            int right = 0;
            while(right < len){
                while(right < len && s.charAt(right) == s.charAt(left)) right++;
                tmp.append(right - left);
                tmp.append(s.charAt(left));
                left = right;
            }
            s = tmp;
        }
        return s.toString();
    }
}
